509 斐波那契数

// 斐波那契数 （通常用 F (n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

// F(0) = 0，F(1) = 1

// F (n) = F (n - 1) + F (n - 2)，其中 n > 1

// 给定 n ，请计算 F (n) 。

示例 1：

输入：n = 2 输出：1 解释：F (2) = F (1) + F (0) = 1 + 0 = 1

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if(n == 0) return 0
    if(n == 1) return 1
    return fib(n-1) + fib(n-2)
};

简单递归

var fib = function (n) {
    let a = new Array(n + 1)
    if (n == 0) return 0
    if (n == 1) return 1
    a[0] = 0
    a[1] = 1
    for (let i = 2; i <= n; i++)
        a[i] = a[i - 1] + a[i - 2]
    return a[n]
};

简单数组动态规划

var fib = function(n) {
    if (n < 2) {
        return n;
    }
    let p = 0, q = 0, r = 1;
    for (let i = 2; i <= n; i++) {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
};

动态规划 初始化：设定初始值 p = 0, q = 0, r = 1。这相当于 F (0) = 0, F (1) = 1。 循环计算： 从 i = 2 开始，直到 i = n。 在每次循环中： 将 p 更新为 q 的值。这意味着 p 保持前一轮 q 的值。 将 q 更新为 r 的值。这意味着 q 保持前一轮 r 的值。 计算新的 r 值，它是 p 和 q 的和。这相当于 F (i) = F (i-1) + F (i-2)。 返回结果：循环结束后，r 就是第 n 个斐波那契数。 通过这种方式，我们只用了常量空间（p, q, r 三个变量）就完成了对斐波那契数的计算，实现了空间复杂度为 O (1) 的算法。

var fib = function (n) {
    const sqrt5 = Math.sqrt(5);
    const fibN = Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n);
    return Math.round(fibN / sqrt5);
};

数学方法

$$x^2=x+1$$$$F(n)=\frac{1}{\sqrt{5}}[{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n]$$

这个公式利用了黄金分割比和其共轭来计算斐波那契数列的第 n 项。